1. Field of the Invention
The present invention relates to a coding apparatus and method and, more particularly, to a coding apparatus and method that are configured to lower the processing load associated with coding and speed up the processing associated with coding.
2. Description of the Related Art
Recently, the LDPC (Low Density Parity Check) code (R. G. Gallager, “Low-density parity-check codes,” IRE Trans. Inform. Theory, vol. IT-8, pp. 21-28, January 1962.) has been receiving attention as an error correction code. The LDPC code is advantageous in that code design is facilitated by providing a particular regularity to a parity check matrix of LDPC code and a circuit for coding and decoding by use of that regularity can be easily configured. Particularly, studies have been being made on many LDPC codes that uses the regularity having a cyclic structure. (For example, refer to Y. Kou, S. Lin, M. P. C. Fossorier, “Low-density parity-check codes based on finite geometries: a rediscovery and new results,” IEEE Trans. Inform. Theory vol. 47, no. 7, pp. 2711-2736, November 2001. and M. Noda, “Designing a self-orthogonal quasi-cyclic code with extended minimum Hamming distance,” Proc. 4th Int. Sympo. Turbo Codes and Related Topics, April 2006.)
A linear block code of length N=pL and information word length K in which each cyclic shift of a code word by p symbols yields another code word is referred to an (N, K) quasi-cyclic code. (For example, refer to R. L. Townsend and E. J. Weldon, Jr., “Self-orthogonal quasi-cyclic codes,” IEEE Trans. Inform. Theory, vol. IT-13, no. 2, pp. 183-195, April 1967. (hereinafter referred to as Non-Patent Document 4)).
Referring to FIG. 1, there is shown an example of a parity check matrix of binary (12, 7) quasi-cyclic code. In the parity check matrix shown in FIG. 1, each sub matrix of 6-by-2 divided by lines is obtained by cyclically shifting down the immediately left-side sub matrix by one row. For example, “1 0” of row 1, column 1 and row 1, column 2 are shifted to row 2, column 3 and row 2, column 4 and “1 0” of row 2, column 1 and row 2, column 2 are shifted to row 3, column 3 and row 3, column 4. Thus, the sub matrix on the immediately left side is cyclically shifted down by one row.
Non-Patent Document 4 shows a configuration of a coding circuit that sequentially outputs parities from a K-stage cyclic shift register and two or more XOR circuits connected thereto. Japanese Patent No. 4045872 (herein after referred to as Patent Document 1) shows a method of the coding to systematic codes by repetitively using p generator polynomials as another coding method quasi-cyclic codes.
The coding method described in Patent Document 1 is based on the property that each code word is expressed by a sum of products of p generator polynomials having different orders and polynomials of xp. Namely, given code polynomial c(x) can be expressed by following equation (1):
                              c          ⁡                      (            x            )                          =                              ∑                          j              =              1                                      p              -              1                                ⁢                                                    g                j                            ⁡                              (                x                )                                      ⁢                                          q                j                            ⁡                              (                                  x                  p                                )                                                                        (        1        )            
In equation (1) above, qj(xp) is a polynomial of xp, gj(x) is a generator polynomial that is a code polynomial having minimum degree with the degree satisfying deg(gj(x)) mode p=j.
Let an information symbol row be [a0 a1 . . . aK−1] and a parity symbol row be [r0 r1 . . . rN−K−1] and define information polynomial a(x) and parity polynomial r(x) by the following equations, respectively:
                              a          ⁡                      (            x            )                          =                              ∑                          j              =              0                                      K              -              1                                ⁢                                    a              j                        ⁢                          x                              K                -                1                -                j                                                                        (        2        )                                          r          ⁡                      (            x            )                          =                              ∑                          j              =              0                                      N              -              K              -              1                                ⁢                                    r              j                        ⁢                          x                              N                -                K                -                1                -                j                                                                        (        3        )            
At this time, systematic-coded symbol row [a0 a1 . . . aK−1 r0 r1 . . . rN−K−1] can be written as code polynomial c(x)=a(x)XN−Kr(x). Therefore, for coding, a parity polynomial that satisfies equation (4) below may be obtained.
                              r          ⁡                      (            x            )                          =                                            a              ⁡                              (                x                )                                      ⁢                          x                              N                -                K                                              -                                    ∑                              j                =                0                                            p                -                1                                      ⁢                                                            g                  j                                ⁡                                  (                  x                  )                                            ⁢                                                q                  j                                ⁡                                  (                                      x                    p                                    )                                                                                        (        4        )            
If a parity check matrix is the quasi-cyclic code shown in FIG. 1, the two generator polynomial may be:g0(x)=x6+x3+x g1(x)=x5+x4+x3+1
FIG. 2 shows an exemplary configuration of a parity generating circuit that satisfies the above-mentioned two generator polynomials. The parity generating circuit 10 shown in FIG. 2 has input terminals 11, 12, flip-flops 13 through 17, output terminals 18, 19, AND circuits 20, 21, and adders 22 through 24.
With the parity generating circuit 10 shown in FIG. 2, information bits a1, a3, a5, 0, 0, 0 are sequentially entered at the input terminal 11 and information bits a0, a2, a4, a6, 0, 0 are entered at the input terminal 12. From the output terminal 18, parity bits r0, r2, r4 are sequentially outputted and, from the output terminal 19, parity bits r1, r3 are sequentially outputted.
Before executing coding, the parity generating circuit 10 initializes all flip-flops 13 through 17 to zero. The information bits are entered in units of two bits with 0 added by the number of parities, during which a control signal is kept at 1.
When the information bits have all been entered in the parity generating circuit 10, the parities are sequentially outputted to the flip-flops 13 through 17, with the control signal being 0. In the feedback from the upper bits of the flip-flops 13 through 17, the coefficient of the generator polynomial corresponds to the place of 1.
FIG. 3 schematically shows a parity generating circuit configured to execute parallel processing on a p symbol basis. FIG. 3 also schematically shows the parity generating circuit 10 shown in FIG. 2. A parity generating circuit 50 shown in FIG. 3 is configured by an (N−K)-stage register 51 and a combinatorial circuit 52.
The combinatorial circuit 52 of the parity generating circuit 50 shown in FIG. 3 is configured to obtain coefficients of sequential qj(xp) from upper p symbols of the (N−K)-stage register 51 and subtract a value obtained by multiplying these p coefficients by the generator polynomial from a register output and new p information symbols, thereby using a subtraction result for a next register input value.
In order to executing coding at higher speeds in the parity generating circuit 50 configured by the above-mentioned one-stage combinatorial circuit 52, the operation clock of the circuit may be increased as one means. However, it is systematically difficult to increase the operation clock higher than 400 MHz for example.
Therefore, in order to executing coding at high speeds, a configuration may be considered in which parallel processing is executed in units of symbols that is a multiple of p. For example, a coding circuit for executing parallel processing in units of 2p symbols can be realized by stacking two parity generating circuits that execute the processing on a p symbol unit as shown in FIG. 2.
FIG. 4 shows a parity generating circuit 100 that executes, in units of 4 bits, parallel processing of the 2-stage of the combinatorial circuit in the parity generating circuit 10 shown in FIG. 2. The parity generating circuit 100 shown in FIG. 4 is configured by input terminals 101 through 104, flip-flops 105 through 109, output terminals 110 through 113, AND circuits 114 through 117, and adders 118 through 127.
With the parity generating circuit 100 shown in FIG. 4, information bits a3, 0, 0 are sequentially entered at the input terminal 101, information bits a0, a4, 0 are sequentially entered at the input terminal 102, information bits a1, a5, 0 are sequentially entered at the input terminal 103, and information bits a2, a6, 0 are sequentially entered at the input terminal 104. Parity bits r0, r4 are outputted from the output terminal 110, parity bit r1 is outputted from the output terminal 111, parity bit r2 is outputted from the output terminal 112, and parity bit r3 is outputted from the output terminal 113.
Before executing coding, the parity generating circuit 100 initializes all flip-flops 105 through 109 to 0. The information bits are entered in units of four bits with 0 added by the number of parities, during which a control signal is kept at 1.
When the information bits have all been entered in the parity generating circuit 100, the parities are sequentially outputted to the flip-flops 105 through 109, with the control signal being 0.
FIG. 5 schematically shows a parity generating circuit 150 that executes, in units of 2p symbols, parallel processing of the 2-stage of the combinatorial circuit 52 in the parity generating circuit 50 shown in FIG. 3 using p generator polynomials. The parity generating circuit 150 shown in FIG. 5 is configured by an (N−K)-stage register 151, a combinatorial circuit 152, and a combinatorial circuit 153.
The two connected combinatorial circuits 152 and 153 are the same in configuration as the combinatorial circuit 52 shown in FIG. 3. The first-stage combinatorial circuit 152 obtains coefficients of sequential qj(xp) from the upper p symbols of the (N−K)-stage register 151. The second-stage combinatorial circuit 153 obtains coefficients of sequential qj(xp) from the upper p symbols in the output from the first-stage combinatorial circuit 152.
Therefore, after the upper p symbols of a result of the subtraction of a value obtained by multiplying p coefficients and generator polynomials in the first-stage combinatorial circuit 152 from the register output have been established, a multiplication is further executed between the second-stage p coefficients and generator polynomials. Because the second-stage operation is started by use of a result of the first-stage operation, a delay is caused by the wait for the result of operation of the first stage, thereby eventually causing a large delay.